[NOIP2014]联合权值

发表于 | 分类于 | | 阅读次数:

题目

题目描述

无向连通图G 有n 个点，n – 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入格式

输入文件名为link .in。
第一行包含1 个整数n 。
接下来n – 1 行，每行包含 2 个用空格隔开的正整数u 、v ，表示编号为 u 和编号为v 的点之间有边相连。
最后1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。

输出格式

输出文件名为link .out 。
输出共1 行，包含2 个整数，之间用一个空格隔开，依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007 取余。
「数据说明」
对于30% 的数据，1 < n≤ 100 ；
对于60% 的数据，1 < n≤ 2000；
对于100%的数据，1 < n≤ 200 , 000 ，0 < wi≤ 10, 000 。

输入样例

1
2
3
4
5
6
5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10

输出样例

1
20 74

题解

这道题其实是道水题（逃ε=ε=ε=┏(゜ロ゜;)┛
我们首先要发现的一点就是如果我们确定了一个点，他所遍历到的所有点它们互相的距离就是$2$。
所以我们就可以枚举每一个点，枚举它每一个可通往的点，最大值取
$$Mx=max(Mx,该点遍历的最大值\times该点遍历到的次大值)$$
而总和我们就取
$$Ans=\sum V[遍历过的边] \times V[当前边]$$
注意要最后答案要乘2，因为(1,3)(3,1)要算两次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 200004, mod = 10007;
int Head[MAXN], Nt[MAXN * 2], to[MAXN * 2];
int tot, n;
int v[MAXN];
int mx, ans;

void add(int a, int b) {
    Nt[++tot] = Head[a];
    to[tot] = b;
    Head[a] = tot;
}

void get(int x) {
    int sum = 0, ma = 0, m = 0;//当前总和，最大值，次大值
    for (int i = Head[x]; i; i = Nt[i]) {
        if (v[to[i]]>ma) { m = ma;    ma = v[to[i]]; }
        else if (v[to[i]]>m)m = v[to[i]];
        ans = (ans + sum * v[to[i]]) % mod;
        sum = (sum + v[to[i]]) % mod;
    }
    mx= max(mx, ma*m);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        get(i);
    }
    cout << mx << " " << ans*2%mod << endl;
    return 0;
}